package net.xuele.learn.dancing;

/**
 * @Author: yubo
 * @date: 14:27 2021/1/5
 * @Description: 类描述：84 接雨水
 */

public class Trap {

    public static int trap1(int[] height) {
        int length = height.length;
        int res = 0;
        for (int i = 0; i < length - 1; i++) {
            int lMax = 0, rMax = 0;
            // 找右边最高的柱子
            for (int j = i; j < length; j++) {
                rMax = Math.max(rMax, height[j]);
            }
            // 找左边最高的柱子
            for (int j = 0; j <= i; j++) {
                lMax = Math.max(lMax, height[j]);
            }
            res += Math.min(lMax, rMax) - height[i];
        }

        return res;
    }

    /**
     * 核心的解法就是看下这根柱子能装多少水，这根柱子能装多少水跟柱子左右最高的柱子有关系，
     * 计算当前柱子的左右高度时需要与自己比较
     *
     * lMax[i]和rMax[i]表示height[0..i]和height[i..end]的最高柱子高度
     *
     *
     * 能装水的量等于min(左边最高,右边最高) - 当前柱子高度
     *
     * @param height
     * @return
     */
    public static int trap2(int[] height) {
        int length = height.length;
        if (length == 0) {
            return 0;
        }
        int res = 0;
        // lMax表示柱子i的左边最高的柱子
        int[] lMax = new int[length];
        // lMax表示柱子i的右边最高的柱子
        int[] rMax = new int[length];
        // 第一个左边最高的柱子就是他自己
        lMax[0] = height[0];
        // 最后一个右边最高的柱子就是他自己
        rMax[length - 1] = height[length - 1];
        // 从左向右计算lMax，从第二个开始算
        for (int i = 1; i < length; i++) {
            // 比较自己和前一个柱子左边的最高点
            lMax[i] = Math.max(height[i], lMax[i - 1]);
        }
        // 从由向左计算rMax，从倒数第二个开始算
        for (int i = length - 2; i >= 0; i--) {
            // 比较自己和后一个柱子右边的最高点
            rMax[i] = Math.max(height[i], rMax[i + 1]);
        }
        for (int i = 1; i < length - 1; i++) {
            // 左右的最矮决定最终能装多少水
            res += Math.min(lMax[i], rMax[i]) - height[i];
        }
        return res;
    }
}
